greatcfandomcom-20200214-history
COS
Co-Operating (Operating) Systems A COS (Cooperating Operating System or Co-Operating System for short) is an operating system where the functionality of the Operating System is spread across many small cooperating OS processors. A COS is the first attempt at building a platform for GREAT Computing. Many influences have been drawn upon in this work. Around 1987 Jason Cozens worked with Ivor Catt at wikipedia:Sinclair Research. The work involved looking at ways to program the Catt Spiral. Some of the things looked at were the use of CSP (Hoare, 1985) to implement Fast Fourier Transforms. The Catt Spiral was a way of addressing the problem of flaws in silcon wafers. A major factor limiting the size of silicon chips is the fact that the probability of a flaw on a silicon chip increases with square of the width of the chip (assuming a square chip). Therefore doubling the width of a chip increases the probability of the chip failing by a factor of 4. This makes the chance of using a whole wafer with today's manufaturing techniques very small. {NOTE: This is a very naive model of flaws , see (Mead, Conway, 1980) for a less naive model.} Catt split the wafer into cells. A cell would be selected on the edge of the wafer and this would probe its neighbouring cells to find one that was working. When a working cell was found this cell would then probe its neighbours. In this way bad cells would be isolated and a chain of good cells would be established. The major problem in programming the Catt Spiral was the limitations of the architecture and the I/O bottleneck. Catt later (Circa 1990) went on to propose The Kernel Logic Machine. This extended the spiral idea to connect up a mesh network of processors. There seems to have been limited interest in this at the time. Also during the late 1980s Jason Cozens was researching into Adaptable Processor Systems. This work was influenced by SUN's wikipedia:NeWS and looked at developing formal models of such systems. As part of this work a claculus of higher order processes was developed but this was too close to Bent Thomsens CHOCS (Thomsen, 1989) to be published. A number of fruitful discussions and meetings were had with Bent Thomsen. Eager Queue Protocols (to be discussed below) were started around 2004 (See OpenEd-Lab4 for some early ideas) as a way of monitoring distributed processes as part of the Child Trust Fund project. Context Application Area - General Purpose Computing The design presented here is targetted at general purpose computing. We are looking for an architecture that provides reasonable performance across many problem domains. The architecture is not aimed specifically at HTC (High Throughput Computing) and in particular is not aimed at computing where the architecture can be optimised before computing starts. Process networks in general purpose computing tend to lack regular structure. It is the intention that a COS can easily configure process networks with irregular structures. Assumptions To simplify the initial development some assumptions have been made. The main assumption that is being made is that there is a large number of processors. This largely removes the need for a scheduler. The assumption is not totally unfounded. In the late 1980s Ivor Catt proposed a Kernel machine with 1,000,000 cores. * Large number of processors ** Catt Kernel http://www.patentstorm.us/patents/5055774.html ** Intel's Single Chip Cloud Computer Design Objectives Reliability and energy efficiency are becoming dominant constraints in the design of computing systems. These are the primary design objectives for a COS. Traditionally the most expensive part of a computer has been the central processing unit. The original computers were expensive from a manufacturing perspective. Modern microprocessors are expensive from an energy perspective. Linking Text In the design of a Co-Operating System we want to aim at satisfying Tanebaum's 3 principles (Tanenbaum, 2001, pp 859-861): * Principle 1: Simplicity * Principle 2: Completeness * Principle 3: Efficiency Development of a COS If we start by looking at the objectives for a platform for GREAT computing we have the following list: * Guaranteed * Reliable * Efficient * Affordable * Testable Guaranteed It is only possible to guarantee a system if there is confidence in it operating correctly. The work on this page mainly relies on guaranteeing that the system meets it specification with (physically) reliable components. A COS can also handle fault tolerance. If the system is fault tolerant a guarantee can have a wider scope. Reliable If we return to the hypothesis for this work, it states: We want an architecture where we can prove our systems correct. It is generally accepted that to enable proofs to be feasible a system must be component based. When working bottom-up we want the PQ cells to be the basic component that provides a foundation. In Can We Make Operating Systems Reliable and Secure? (Tanenbaum et al., 2006) the authors consider 4 attempts at improving the reliability and security of operating systems: # Armored Operating Systems # Paravitual machines # Microkernels # Singularity Approaches 1 and 2 are intended to improve the reliability of existing (legacy) systems. 3 and 4 replace legacy operating systems with more reliable and secure ones. The multiserver approach runs each driver and operating system component in a separate user process nd allows them to communicate using the microkernel's IPC mechanism. Finally, Singularity, the most radical approach, uses a type-safe language, a single address space, and formal contracts to carefully limit what each module can do. A COS makes the basic component a process and isolates the process in hardware. Some of the ideas here come form the Singularity project (Hunt, Larus, 2007). In singularity processes run as software isolated processes. In a COS processes run as hardware isolated processes. Much of the work in singularity seems to reflect work based on the transputer. The main difference would appear to be that singularity is a more general purpose OS. Guarantees and Reliability - Need Reworking It is not easy to guarantee systems which are not reliable. Therefore the first objective for a COS is reliability. If we can build reliable systems we can guarantee them and meet the GR objectives. Refactoring the Microkernel The following diagram is from (Tanenbaum, 2001): Good system design consists of separate concerns that can be combined independently. (Tanenbaum, 2001, pp 871) In the design of a Co-Operating System we want to try and treat IPC, Process Management and Scheduling as orthogonal concepts. We start by separating process management and IPC using an IPC network. At the same time we note that process management can be broadened to resource management. Later we will broaden process management to include management of the IPC network. We have stated earlier that a major working assumption initially is that there is a large number of processors, We therefore run each server on its own processor and at the same time split the process management onto separate processors. In the diagram above it is not shown how the process managers communicate. The process managers are going to communicate over a dedicated broadcast network. At this point we also rename the process managers as QCells. The QCells are much smaller than the main processors. For the moment we also do not worry too much about the IPC network. Below we will show how the network can be managed in a similar way to the processors and also how processes working together can be kept in local proximity with each other. Basic PQ-Cells A PQ-Cell is a pair consisting of the Processor, P and the OS cell Q. In a basic PQ-Cell the Q-Cell is responsible for the management of processes running on the processors. Processors (P-Cells) communicate across an IPC (Inter Processor Network) network, this is mainly point to point. The Q-Cells communicate across an IQC (Inter Q-Cell Communication) network, this a broadcast network dedicated solely to the Q-Cells. Each PQ-Cell pair has a private communication channel. Given that we are assuming: * A large pool of processors * One process per processor Process management becomes a matter of: * Finding an available processor when there is a fork * Making a processor available when its process terminates. To do this the Q-Cells manage a queue of available processors. Each Q-Cell has a copy of the queue. When a process wants to fork: * The process running on P_1 makes a request to its QCell, Q_1 * Q_1 broadcasts a REQUEST * Q_2 managing the processor at the front of the queue, P_2 , broadcasts an ACCEPT * Q_1 notifies P_1 of the address of P_2 , Q_2 readies P_2 : \; P_4, \; P^*_1, \; P_5, \; P_3 : \; P_4, P^*_1, \; P_5, \; P_3 : \; P^*_2, \; P_4, P^*_1, \; P_5 QCells * Explain Eager Queues Explain Eager Queue Protocols Eager Queue Protocols were developed as a way of monitoring the state of distributed processors. What was wanted was an idea of how "live" the processors were. The first approach was to have each processor transmit a heartbeat and a record was kept of the heartbeats. The initial idea was to keep the record centrally, then it appeared better to have each processor keep its own copy of the heartbeat history. The heartbeat history or last known transmission vector would be an array of processor Ids and when the processor last transmitted, The last known transmission vector could be simplified if the heartbeats across the network were regular. The least recent processor to transmit would be the next expected processor to transmit. If this is the case only a queue of processor Ids is required with the most recent transmitter at the front and the least recent transmitter at the back. When a processor transmits it moves its processor Id to the front of the queue (hence the name Eager Queue at the processor at the back pushes to the front). The following diagram is a state transition diagram for a QCell. The states in the diagram are: * A - Accepting * B - Busy * D - Declining * E - Exiting * H - Holding * I - Idling * J - Joining * L - Listening * N - Not Accepting * Q - Queuing * R - Requesting * W - Waiting * Explanation of REQUEST -> ACCEPT * Image of REQUEST -> ACCEPT A Broadcast Calculus Definition of a Q-Cell An early outline of A Broadcast Calculus is given in Two Ticks, a simulation of a simple Eager Queue Protocol (Cozens, 2008). I - Idling When a Q-Cell is idling it ignores all broadcasts and waits for a Join() command. The Join() command comes from an external source. Following the Join() command the Q-Cell goes into a listening state. : \begin{array}{rcrcl} Idling_i & = & t & . & Idling_i \\ & + & ??UPDATE(q) & . & Idling_i \\ & + & ??JOIN(q) & . & Idling_i \\ & + & ??EXIT(q) & . & Idling_i \\ & + & ??REQUEST(q) & . & Idling_i \\ & + & ??ACCEPT(q) & . & Idling_i \\ & + & ??DECLINE(q) & . & Idling_i \\ & + & Join() & . & Listening_{i,0} \end{array} L - Listening The equation for the listening state is as follows. : \begin{array}{rcrcl} Listening_{i,0} & = & t & . & Listening_{i,1} \\ & + & ??UPDATE(q) & . & Joining_i(q) \\ & + & ??JOIN(q) & . & Joining_i(q) \\ & + & ??EXIT(q) & . & Joining_i(q) \\ & + & ??DECLINE(q) & . & Holding_i(q) \\ & + & ??DECLINE([]) & . & Holding_i([]) \\ & + & ??ACCEPT(q) & . & Joining_i(q) \\ & + & ??REQUEST(q) & . & Holding_i(q) \\ \\ Listening_{i,1} & = & t & . & Joining_i([]) \\ & + & ??UPDATE(q) & . & Joining_i(q) \\ & + & ??JOIN(a) & . & Joining_i(a) \end{array} We have assumed that there is a broadcast every other tick. The Q-Cell in the listening states waits to see if there are any other Q-Cells broadcasting. If there are not it goes into a new Joining state. : t.t.Joining_i([]) If the broadcast channel is active there are several possibilities. J - Joining : \begin{array}{rcrcl} Joining_i(q) & = & !!JOIN(P_i + q) & . & Queuing_i(0,P_i + q) \\ & + & ??JOIN(q') & . & Joining_i(q') \\ & + & ??EXIT(q') & . & Joining_i(q') \\ & + & ??REQUEST(q') & . & Holding_i(q') \end{array} Q - Queuing : \begin{array}{rcrcl} Queuing_{i,0}(q) & = & t & . & Queuing_{i,1}(q) \\ & + & ??JOIN(q') & . & Queuing{i,0}(q') \\ & + & ??EXIT(q') & . & Queuing_i(q') \\ & + & ??REQUEST(q') & . & Accepting_i(q') \\ & + & Exit() & . & Exiting_{i,0}(q) \\ \\ Queuing_{i,1}(q + P_i) & = & !!UPDATE(P_i + q) & . & Queuing_{i,0}(P_i + q) \\ \\ Queuing_{i,1}(q) & = & ??UPDATE(q') & . & Queuing_{i,0}(q') \\ & + & ??EXIT(q') & . & Queuing{i,0}(q') \\ & + & Exit() & . & Exiting_{i,1}(q) \end{array} A - Accepting : \begin{array}{rcrcl} Accepting_i(P_i + q) & = & !!ACCEPT(P^*_i + q) & . & Busy_i(P^*_i + q) \\ \\ Accepting_i(q) & = & ??DECLINE(q') & . & Accepting_i(q') \\ & + & ??ACCEPT(q') & . & Queuing_i(q') \\ & + & Exit() & . & Declining_i(q) \end{array} E - Exiting B - Busy : \begin{array}{rcrcl} Busy_i(q) & = & Request() & . & Requesting_i(q) \\ & + & t & . & Busy_i \\ & + & ??UPDATE(q') & . & Busy_i(q') \\ & + & ??JOIN(q') & . & Busy_i(q') \\ & + & ??EXIT(q') & . & Busy_i(q') \\ & + & ??REQUEST(q') & . & Busy_i(q') \\ & + & ??ACCEPT(q') & . & Busy_i(q') \\ & + & ??DECLINE(q') & . & Busy_i(q') \\ & + & Free() & . & Joining_i(q) \end{array} D - Declining R - Requesting Waiting needs changing to Requesting. : \begin{array}{rcrcl} Requesting_i(0) \end{array} Efficient Up to this point we have been looking at a COS from the perspective of reliability. Of equal importance to reliability is efficiency. We look at the management of energy efficiency from two perspectives. * Control of the P Cell energy use by their Q cells. * Control of the QCell network energy use by the QCell network. Control of P Cell Energy Use * Image of QCell acting as a proxy. Contol of the QCell Network Energy Use So far we have considered how a QCell can control the state of its P co-processor. This still leaves a problem. If we have a network of 1,000,000 PQ-Cells then when the system is in an idling state there will still be 1,000,000 QCells running. However as each QCell knows the state of the system QCells can power one another on and off. This has similarities to the Game of Life Conway's_Game_of_Life. The main difference being that QCell that are running have a much more state information. We add control lines in as show in the following diagram. This PQ-Cell is then replicated. Control of Number of QCells with Fixed Reference Now that QCells can control the state of their neighbours we need to consider how this is managed. A simple scenario would be to require a fixed number of idling cells, N-R is the required number. The current number of idling cells (N-I) is then fed back and the difference (N-R - N-I) is used to control the QCells. This feedback is limited by the fact that N-R is a constant or at least is provided by an external source. Control of Number of QCells with Dynamic Reference It is likely that the number of idling processors will want to be higher when there are more busy processors. N-R can be made dynamic by basing it on the number of busy processors N-B. Control of Number of QCells with Adaptive Reference Affordable Throughout the design of a COS one of the design objectives has been Simplicity. The architecture presented is based around 1 type of cell. This greatly simplifies the detailed implementation. This should reduce manufacturing costs. From a programmability point of view current software can be gradually migrated to take adavantage of the COS architecture. It should be possible to expose a POSIX API to programs running on a COS. Testable Notation Processors will be denoted by P_{Id} where a capital P indicates a processor and Id is the identity (address) of the processor. A processor that is busy (i.e. is running a process) will have a superscript asterisk, P^* . Queues Queues will use standard list notation (cf. python): * [ \; ] is the empty queue. * \; P_2, \; P_3, \; P_4 is a queue with 4 members, P_1 is at the front of the queue, P_4 is at the back. ''Temporary Notes'' * Transputer * Singularity * Microkernel * Law of Demeter * Catt Spiral/Kernel * CSK * Per Brinch Hansen The main service of an operating system is process management. Process management consists of: * Creating Processes * Scheduling Processes * Destroying Processes Key Points # COS is aimed at general purpose computing. # Separates the Operating System from the Applications # Decentralised # Aims to run with Just Enough Power # Fast Boot as each process boots in parallel # Processes run on isolated Processors (cores) # Simple Cell Architecture - PQ Cells Relation to Microkernels A COS is very similar to a Microkernel in that it tries to implement the minimal functionality. wikipedia:Microkernel#Essential_components_and_minimality Microkernel - Essential Components and Minimality It states as a microkernel must allow building arbitrary operating system services on top, it must provide some core functionality. At the least this includes: # some mechanisms for dealing with address spaces — this is required for managing memory protection; # some execution abstraction to manage CPU allocation — typically threads or scheduler activations; and # inter-process communication — required to invoke servers running in their own address spaces. This minimal design was pioneered by Brinch Hansen's Nucleus (Brinch Hansen, 1970) and the hypervisor of IBM's VM. A COS satisfies these as follows: # Processes run on separate processors, this provides the first part of memory protection. # The execution abstraction is parallel processors. # This is an open question at the moment. There are several possible approaches. Process Granularity A COS Architecture Difficulties in Implementing a COS See Also Operating System Research Category:Research